package algorithm;

import algorithm.utils.*;


/**
 * @author ：蔡博
 * @description：TODO
 * @date ：2022/11/19 22:49
 */
public class BinaryTreeMaxPathSum124 {
    int res;
    public int maxPathSum(TreeNode root) {
        res = root.val;
        dfs(root);
        return res;
    }
    int maxRoot(TreeNode root){
        if(root.left==null&&root.right==null){
            return root.val;
        }
        int l=0;
        int r=0;
        if(root.left!=null)
            l = maxRoot(root.left);
        if(root.right!=null)
            r = maxRoot(root.right);
        System.out.println(Math.max(l,r)+root.val);
        return Math.max(0,Math.max(l,r))+root.val;
    }
    void dfs(TreeNode root){
        if(root.left==null&&root.right==null)
            res = Math.max(res,root.val);
        if(root.left!=null&&root.right!=null)
            res=Math.max(res,Math.max(0,maxRoot(root.left))+root.val+Math.max(0,maxRoot(root.right)));
        if(root.left!=null){
            res = Math.max(res,Math.max(0,maxRoot(root.left))+root.val);
            dfs(root.left);
        }
        if(root.right!=null){
            res = Math.max(res,Math.max(0,maxRoot(root.right))+root.val);
            dfs(root.right);
        }
    }
    public static void main(String[] args) {
        Integer[] array = {
                -622,-37,90,567,-516,832,-487,-59,953,null,436,-174,130,null,-330,null,253,-211,-648,null,null,-524,null,-428,-245,717,-742,null,null,null,null,null,null,null,null,731,-406,-357,-616,-810,-191,615,327,223,-506,-113,558,743,699,824,null,-727,285,-914,null,null,481,-477,786,null,null,394,null,-225,null,null,235,-309,null,2,-362,208,null,null,202,null,null,-164,211,506,-450,-581,null,null,-522,-867,-140,93,-593,-483,969,354,-148,null,null,null,-921,-738,null,null,-45,-570,null,null,546,-421,-112,null,null,null,null,616,null,466,744,740,36,-218,993,935,-719,-293,-555,null,331,616,null,-961,529,null,null,null,-368,null,82,null,-17,null,null,null,null,493,-741,null,null,-973,-694,412,null,-511,null,-678,121,null,-985,null,-270,null,null,null,null,null,83,-802,null,-538,null,null,null,-538,674,null,64,-623,null,null,279,null,null,null,null,null,null,-43,null,331,229,937,-669,null,-608,-185,null,null,-879,-115,328,-966,null,null,null,-60,null,null,null,766,-63,645,null,-657,-848,null,null,null,null,-894,null,239,null,255,120,null,-91,null,934,null,null,null,-393,null,null,null,null,null,null,542,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,305,53,null,-660,null,null,null,245,null,null,null,-200,904,null,null,null,-959,null,590,759,null,-518,null,null,null,-868};
        TreeNode root = BuildTree.processTreeNode(array);
        BinaryTreeMaxPathSum124 c = new BinaryTreeMaxPathSum124();

        System.out.println(c.maxPathSum(root));
    }
}
